package com.cwj.lab3;

import com.cwj.lab1.myArrayList;

public class Dijkstra {
    //用来存储结点的结点，其通过索引对应图中的结点
    class Node{
        int close;//最短距离的邻接点
        int lowest;//目前确定的到给定点的最短记录

        public Node(int close, int lowest) {
            this.close = close;
            this.lowest = lowest;
        }
    }
    Node[]pathSmall;//用来存储最短距离的路径和数组
    int st;//单源最短路径的源点

    /**
     * 求单源最短路径
     * */
    public Node[] smallestPath(Graph_matrix graph,int start){
        int V_NUM=graph.getV_num();
        Node[]list=new Node[V_NUM];
        //初始化list，其也是最后的pathSmall
        for (int i = 0; i <V_NUM; i++) {
            list[i]=new Node(start,graph.getVal(start,i));
        }
        //n-1次选取确定点的最短路径
        Node nn=null;
        for (int i = 0; i < V_NUM-1; i++) {
            int min=Integer.MAX_VALUE,ind=-1;
            for (int j = 0; j < V_NUM; j++) {
                nn=list[j];
                if(nn.lowest!=0){
                    if(min>nn.lowest){
                        min=nn.lowest;
                        ind=j;//nn.close;
                    }
                }
            }
            nn=list[ind];
            //松弛
            for (int j = 0; j < V_NUM; j++) {
                int ij=0,inf=graph.getINF();
                if(list[j].lowest!=0&&(ij=graph.getVal(ind,j))!=inf){
                    int temp=nn.lowest+ij;
                    if(list[j].lowest>temp){
                        list[j].lowest=temp;
                        list[j].close=ind;
                    }
                }
            }
            nn.lowest=0;
        }
        this.st=start;
        return pathSmall=list;
    }
    /**将每个结点的最短路径化为线性表输出*/
    public myArrayList<myArrayList<Integer>> toList(){
        myArrayList<myArrayList<Integer>>paths=new myArrayList<>();
        int tt=0;
        for (int i = 0; i < this.pathSmall.length; i++) {
            paths.addLast(new myArrayList<>());
            System.out.print("结点"+i+"的最短路径:");
            tt=i;
            while(tt!=this.st){
                paths.back().addLast(tt);
                tt=pathSmall[tt].close;
            }
            paths.back().addLast(this.st);
            System.out.println(paths.back());
        }
        return paths;
    }
}
